package solution;

import utils.IPrint;

/**
 * @author or2
 * @date 2021年7月19日 21点27分
 */
public class ReversePairs {

    public static <E extends Comparable<E>> int resolve(E[] arr) {
//        全局辅助数组, 节约空间和new对象的事件
        E[] auxArr = arr.clone();
        int resolve = resolve(arr, 0, arr.length - 1, auxArr);
        IPrint.printWithColorNoBg("逆序数个数为: " + resolve);
        return resolve;
    }

    /**
     * 使用 归并排序 解决逆序数问题
     * @param arr 原数组
     * @param startIndex 递归数组起始下标
     * @param endIndex 递归数组终止下标
     * @param auxArr 全局辅助数组
     * @param <E> 实现可排序 {@code Comparable} 接口的泛型
     * @return 本次递归累加的逆序数
     */
    private static <E extends Comparable<E>> int resolve(E[] arr, int startIndex, int endIndex, E[] auxArr) {
//        递归终止条件
        if (startIndex >= endIndex) {
            return 0;
        }
        int sum = 0;

        int mid = startIndex + (endIndex - startIndex >> 1);
        sum += resolve(arr, startIndex, mid, auxArr);
        sum += resolve(arr, mid + 1, endIndex, auxArr);

//        优化: 无序时才进行合并排序
        if (arr[mid].compareTo(arr[mid + 1]) > 0) {
            sum += merge(arr, startIndex, mid, endIndex, auxArr);
        }
        return sum;
    }

    /**
     * 对有序数组 {@code arr[startIndex, mid], arr[mid + 1, endIndex]} 进行合并
     * @param arr 原数组
     * @param startIndex 数组①起点下标
     * @param mid 数组①终点下标, +1后为数组②起点下标
     * @param endIndex 数组②终点下标
     * @param auxArr 全局辅助数组
     * @param <E> 实现可排序 {@code Comparable} 接口的泛型
     * @return 本次合并求得的逆序数
     */
    private static <E extends Comparable<E>> int merge(E[] arr, int startIndex, int mid, int endIndex, E[] auxArr) {
//        使用全局辅助数组进行拷贝
        System.arraycopy(arr, startIndex, auxArr, startIndex, endIndex - startIndex + 1);
        int sum = 0;
        int lIndex = startIndex, rIndex = mid + 1;
        for (int i = startIndex; i <= endIndex; i++) {
            if (lIndex > mid) {
                arr[i] = auxArr[rIndex];
                rIndex++;
            } else if (rIndex > endIndex) {
                arr[i] = auxArr[lIndex];
                lIndex++;
            } else if (auxArr[lIndex].compareTo(auxArr[rIndex]) < 0) {
                arr[i] = auxArr[lIndex];
                lIndex++;
            } else {
                sum += mid - lIndex + 1;
                arr[i] = auxArr[rIndex];
                rIndex++;
            }
        }
        return sum;
    }

}
